//<p>给定一个未排序的整数数组 <code>nums</code> ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。</p>
//
//<p>请你设计并实现时间复杂度为 <code>O(n)</code><em> </em>的算法解决此问题。</p>
//
//<p> </p>
//
//<p><strong>示例 1：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [100,4,200,1,3,2]
//<strong>输出：</strong>4
//<strong>解释：</strong>最长数字连续序列是 <code>[1, 2, 3, 4]。它的长度为 4。</code></pre>
//
//<p><strong>示例 2：</strong></p>
//
//<pre>
//<strong>输入：</strong>nums = [0,3,7,2,5,8,4,6,0,1]
//<strong>输出：</strong>9
//</pre>
//
//<p> </p>
//
//<p><strong>提示：</strong></p>
//
//<ul>
//	<li><code>0 <= nums.length <= 10<sup>5</sup></code></li>
//	<li><code>-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup></code></li>
//</ul>
//<div><div>Related Topics</div><div><li>并查集</li><li>数组</li><li>哈希表</li></div></div><br><div><li>👍 1301</li><li>👎 0</li></div>

package com.rising.leetcode.editor.cn;

import java.util.HashSet;
import java.util.Set;

/**
 * 最长连续序列
 * @author DY Rising
 * @date 2022-06-27 16:25:26
 */
public class P128_LongestConsecutiveSequence{
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P128_LongestConsecutiveSequence().new Solution();
        System.out.println(solution.longestConsecutive(new int[]{9,1,4,7,3,-1,0,5,8,-1,6}));
    }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        //去重
        for (int num : nums) {
            set.add(num);
        }
        //定义最长连续和当前连续
        int maxConsecutive = 0;
        int currentConsecutive = 1;

        for (int num : set) {
            //核心点
            //只有当前数字的前一个连续数字不在集合里面，才会去计算最长连续
            if (set.contains(num - 1)) continue;
            while (set.contains(num + 1)) {
                num += 1;
                currentConsecutive += 1;
            }
            maxConsecutive = Math.max(maxConsecutive, currentConsecutive);
            currentConsecutive = 1;
        }
        return maxConsecutive;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
